package lanqiao;
/**
 * 算法提高 01背包
 * 给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个.
 *
 * 输入的第一行包含两个整数n, m，分别表示物品的个数和背包能装重量。
 * 以后N行每行两个数Wi和Vi,表示物品的重量和价值
 * 输出1行，包含一个整数，表示最大价值。
 * 输入：
 *     3 5
 *     2 3
 *     3 5
 *     4 7
 * 输出：
 *     8
 */
//动态规划
import java.util.Scanner;
public class ADV_144_1 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt(); // 物品个数
        int m = input.nextInt(); // 背包能装重量

        int[] weight = new int[n+1]; //物品的重量
        int[] val = new int[n+1]; //物品的价值
        for(int i=1; i<=n; i++) {
            weight[i] = input.nextInt(); //第i个物品的重量
            val[i] = input.nextInt(); //第i个物品的价值
        }

        //前i个物品放入容量为j的背包的最大价值
        int[][] dp = new int[n+1][m+1];
        /**
         * 重量 价值  背包容量是5
         *  2   3
         *  3   5
         *  4   7
         *
         * 背包容量 0  1  2  3  4  5
         * 前0个   0  0  0  0  0  0
         * 前1个   0  0  3  3  3  3
         * 前2个   0  0  3  5  5  8
         * 前3个   0  0  3  5  7  8
         */
        //i=0时，前0个物品，最终价值一定为0
        //j=0时，背包容量为0,最终价值一定为0
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                //不放第i个物品的情况
                dp[i][j] = dp[i-1][j];
                //放第i个物品的情况
                if(j >= weight[i]){
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight[i]] + val[i]);
                }
            }
        }
        System.out.println(dp[n][m]);
    }
}